/*
题目: 移掉K位数字
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
https://leetcode.cn/problems/remove-k-digits/
 */
public class RemoveKdigits {
    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<> ();
        int len = num.length();

        for (int i = 0; i < len; i++) {
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > num.charAt(i)) {
                deque.pollLast();
                k --;
            }
            deque.offerLast(num.charAt(i));
        }

        //处理掉多余的K
        while (!deque.isEmpty() && k > 0) {
            deque.pollLast();
            k--;
        }

        while (!deque.isEmpty() && deque.peekFirst() == '0') {
            deque.pollFirst();
        }
        if (deque.isEmpty()) {
            return new String("0");  //如果去掉前置0, 就没有元素了, 那就说明是0
        }

        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.pollLast());
        }
        return sb.reverse().toString();
    }
}
